package com.itheima.leetcode.od.b.dynamicprogramming.slidingwindow;

import java.util.Arrays;

/**
 * <h3>宽度最小的子矩阵</h3>
 * 给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数。
 * <p>
 * 输入描述 第一行输入两个正整数N，M，表示矩阵大小。
 * <p>
 * 接下来N行M列表示矩阵内容。下一行包含一个正整数K。下一行包含K个整数，表示所需包含的数组，K个整数可能存在重复数字。
 * <p>
 * 所有输入数据小于1000。
 * <p>
 * 输出描述 输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1
 * <p>
 * 示例1
 * <p>
 * 输入
 * <p>
 * 2 5
 * <p>
 * 1 2 2 3 1
 * <p>
 * 2 3 2 3 2
 * <p>
 * 3
 * <p>
 * 1 2 3
 * <p>
 * 输出 2
 * <p>
 * 说明
 * <p>
 * 矩阵第0、3列包含了1、2、3，矩阵第3、4列包含了1、2、3
 * <p>
 * 示例2
 * <p>
 * 输入
 * <p>
 * 2 5
 * <p>
 * 1 2 2 3 1
 * <p>
 * 1 3 2 3 4
 * <p>
 * 3
 * <p>
 * 1 1 4
 * <p>
 * 输出
 * <p>
 * 5
 * <p>
 * 说明
 * <p>
 * 矩阵第1,2,3,4,5列包含了1,1,4
 */
public class SmallestWidthSubmatrix {
    public static void main(String[] args) {

        int[] params = Arrays.stream("2 5".split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = params[0];
        int m = params[1];

        int[][] matrix = Arrays.stream("1 2 2 3 1\r\n2 3 2 3 2".split("\r\n"))
                .map(str -> Arrays.stream(str.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        int k = Integer.parseInt("3");
        int[] nums = Arrays.stream("1 2 3".split(" ")).mapToInt(Integer::parseInt).toArray();

        System.out.println(getResult(n, m, matrix, k, nums));
    }

    /**
     * 滑动窗口
     *
     * @param n
     * @param m
     * @param matrix
     * @param k
     * @param nums
     * @return
     */
    public static int getResult(int n, int m, int[][] matrix, int k, int[] nums) {
        //每一列，出现数字的个数
        int[][] count_map = new int[m][1000];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count_map[j][matrix[i][j]] += 1;
            }
        }

        int[] target_map = new int[1000];
        for (int i = 0; i < k; i++) {
            target_map[nums[i]] += 1;
        }

        int[] cur_count_map = new int[1000];
        int width = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;

        while (right < m) {
            for (int i = 0; i < 1000; i++) {
                cur_count_map[i] += count_map[right][i];
            }
            while (check(cur_count_map, target_map)) {
                width = Math.min(width, right - left + 1);

                for (int i = 0; i < 1000; i++) {
                    cur_count_map[i] -= count_map[left][i];
                }

                left += 1;
            }
            right += 1;
        }

        if (width == Integer.MAX_VALUE) {
            return -1;
        } else {
            return width;
        }
    }

    public static boolean check(int[] cur_map, int[] target_map) {
        for (int i = 0; i < 1000; i++) {
            if (cur_map[i] < target_map[i]) {
                return false;
            }
        }
        return true;
    }
}